package com.lx.algorithm.Tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-11-08 13:25:26
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-11-08     张李鑫                     1.0         1.0 Version
 */
public class SerializableTree {

    /**
     * 先序 遍历的序列化与反序列化
     *
     * @param tree
     * @return
     */
    public static Queue<String> serializableBefore(Node<Integer> tree) {
        Queue<String> list = new LinkedList<>();
        processBefore(tree, list);
        return list;
    }

    public static Node DeserializationBefore(Queue<String> list) {
        String poll = list.poll();
        if (poll.equals("#")) {
            return null;
        }
        Node<Integer> node = new Node<>(Integer.parseInt(poll));
        node.left = DeserializationBefore(list);
        node.right = DeserializationBefore(list);
        return node;
    }


    public static void processBefore(Node tree, Queue<String> list) {
        if (tree == null) {
            list.add("#");
        } else {
            list.add(String.valueOf(tree.value));
            processBefore(tree.left, list);
            processBefore(tree.right, list);
        }
    }


    public static void process(Node tree) {
        if (tree == null) {
            return;
        }
        System.out.print(tree.value+",");
        process(tree.left);
        process(tree.right);
    }


    /**
     * <p>
     * 按层的方式序列化
     * </p>
     *
     * @param tree
     * @return void
     * @Author zlx
     * @date 2021/11/8
     */
    public static Queue<String> serializableTreeByLevel(Node tree) {
        if (tree == null) {
            return null;
        }
        LinkedList<String> nodes = new LinkedList<>();

        Queue<Node> list = new LinkedList<>();
        list.add(tree);
        nodes.add(String.valueOf(tree.value));
        while (!list.isEmpty()) {
            Node poll = list.poll();
            if (poll.left != null) {

                nodes.add(String.valueOf(poll.left.value));
                list.add(poll.left);
            } else {
                nodes.add(null);
            }
            if (poll.right != null) {
                nodes.add(String.valueOf(poll.right.value));
                list.add(poll.right);
            } else {
                nodes.add(null);
            }
        }
        return nodes;
    }

    public static Node deSerializableTreeByLevel(Queue<String> tree) {
        if (tree.isEmpty()) {
            return null;
        }
        Queue<Node> nodes = new LinkedList<>();
        String poll = tree.poll();
        Node<Integer> node = new Node<>(Integer.parseInt(poll));
        nodes.add(node);

        while (!nodes.isEmpty() && !tree.isEmpty()) {
            Node cur = nodes.poll();

            String treePoll = tree.poll();
            cur.left = treePoll == null ? null : new Node(Integer.parseInt(treePoll));
            if (cur.left != null) {
                nodes.add(cur.left);
            }
            treePoll = tree.poll();
            cur.right = treePoll == null ? null : new Node(Integer.parseInt(treePoll));
            if (cur.right != null) {
                nodes.add(cur.right);
            }
        }

        return node;
    }


    public static void main(String[] args) {
        Node<Integer> a = new Node<>(1);
        Node<Integer> b = new Node<>(2);
        Node<Integer> c = new Node<>(3);
        Node<Integer> d = new Node<>(4);
        Node<Integer> e = new Node<>(5);
        Node<Integer> f = new Node<>(6);
        Node<Integer> g = new Node<>(7);
        a.left = b;
        a.right = c;

        b.left = d;
        b.right = e;
        c.left = f;
        c.right = g;

        process(a);
        System.out.println();

        Queue list = serializableTreeByLevel(a);
        Node node = deSerializableTreeByLevel(list);
        process(node);

    }
}
